#include<iostream>
using namespace std;
long long f(long long x,long long y,long long p){
	if(y==0){
		return 1%p;
	}else if(y%2==0){
		long long temp = f(x,y/2,p);
		return temp*temp;
	}else{
		long long temp = f(x,y/2,p);
		return temp*temp%p*x%p;
	}
}
int main(){
	int t;
	long long x,y,p;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld%lld",&x,&y,&p);
		printf("%lld\n",f(x,y,p));
	}
	return 0;
}
